/**
 * 
 */
package leetCode;


/**
 * @author zhongfang
 *
 */
public class MinimumDepthofBinaryTree {
	  public static class TreeNode {
		      int val;
		      TreeNode left;
		      TreeNode right;
		      TreeNode(int x) { val = x; }
		  }
    public int minDepth(TreeNode root) {
        if(root==null)
            return 0;
        return minD(root);
    }
    
    private int minD(TreeNode root){
        if(root==null){
            return Integer.MAX_VALUE;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        int left=minD(root.left);
        int right=minD(root.right);
        return (left<right?left:right)+1;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TreeNode node1=new TreeNode(1);
		TreeNode node2=new TreeNode(2);
		node1.right=node2;
		MinimumDepthofBinaryTree minimumDepthofBinaryTree=new MinimumDepthofBinaryTree();
		System.out.println(minimumDepthofBinaryTree.run(node1));
//		HashMap<Integer, Integer> freq=new HashMap<>();
//		freq.merge(1, newVal, (oldVal,newVal)->(oldVal+1));
//		ArrayList<Integer> list=new ArrayList<>();
//		Collections.binarySearch(list, 1);
	}
	   public int minDepth=Integer.MAX_VALUE;
	    public int run(TreeNode root) {
	        if(root==null){
	            return 0;
	        }
	        helper(root,1);
	        return minDepth;
	    }
	    
	    public void helper(TreeNode root,int curDepth){
	        if(root==null){
	            return;
	        }
	        if(root.left==null&&root.right==null){
	            if(minDepth>curDepth){
	               minDepth=curDepth;
	            }
	            return;
	        }
	        
	        helper(root.left,curDepth+1);
	        helper(root.right,curDepth+1);
	    }
}
